`
https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function (preorder) {
  // bst的中序就是有序的，然后照搬前序和中序构造二叉树即可
  const inorder = preorder.toSorted((a, b) => a - b)

  // 存储 inorder 值到索引的映射
  const valToIdx = {}
  for (let i = 0; i < inorder.length; i++) {
    valToIdx[inorder[i]] = i
  }

  // 构造二叉树
  return build(
    preorder, 0, preorder.length - 1,
    inorder, 0, inorder.length - 1
  )

  // 给定一个前序遍历数组的范围和一个中序遍历数组的范围
  // 根据这两个范围确定的子数组构建出一颗二叉树，并返回根节点
  function build(
    preorder, preStart, preEnd,
    inorder, inStart, inEnd
  ) {
    // 需要构建的数组长度为 0，即不需要构建，返回 null
    if (preStart > preEnd) {
      return null;
    }

    // 获取根节点的值
    const rootVal = preorder[preStart]

    // 获取根节点的值在 inorder 对应的索引
    const index = valToIdx[rootVal]

    // 计算出子结点（子数组）的长度
    const size = index - inStart

    // 创建根节点
    const root = new TreeNode(rootVal)

    // 递归构造左右子树
    root.left = build(
      preorder, preStart + 1, preStart + size,
      inorder, inStart, index - 1
    )
    root.right = build(
      preorder, preStart + size + 1, preEnd,
      inorder, index + 1, inEnd
    )

    return root
  }
};